package com.leetcode.algorithm.y19.m02;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * leetcode-cn.com
 * (done)20. 有效的括号
 * (done)496. 下一个更大元素 I
 * (done)682. 棒球比赛
 * (done)844. 比较含退格的字符串
 * @author: jie.deng
 * @time: 2019年2月18日 上午11:36:33
 */
public class MySolution0218 {
	
	/**
	 * 20. 有效的括号 
	 * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
	 * 
	 * 有效字符串需满足： 
	 * 左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。 
	 * 注意空字符串可被认为是有效字符串。
	 * 
	 * @param s
	 * @return
	 */
	public boolean isValid(String s) {
		if (s == null || "".equals(s)) {
			return true;
		}
		Stack<Character> stack = new Stack<Character>();
		int len = s.length();
		for (int i = 0; i < len; i++) {
			char ch = s.charAt(i);
			switch (ch) {
			case '(':
			case '{':
			case '[':
				stack.push(ch);
				break;
			case ')':
				if (!stack.isEmpty() && stack.pop() == '(') {
					break;
				} else {
					return false;
				}
			case '}':
				if (!stack.isEmpty() && stack.pop() == '{') {
					break;
				} else {
					return false;
				}
			case ']':
				if (!stack.isEmpty() && stack.pop() == '[') {
					break;
				} else {
					return false;
				}
			default:
				return false;
			}
		}
		return stack.isEmpty();
	}
	
    /**
     * 496. 下一个更大元素 I
     * 给定两个没有重复元素的数组 nums1 和 nums2 ，其中nums1 是 nums2 的子集。找到 nums1 中每个元素在 nums2 中的下一个比其大的值。
     * 
     * nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在，对应位置输出-1。
     * 
     * 示例 1:
     * 
     * 输入: nums1 = [4,1,2], nums2 = [1,3,4,2].
     * 输出: [-1,3,-1]
     * 解释:
     *     对于num1中的数字4，你无法在第二个数组中找到下一个更大的数字，因此输出 -1。
     *     对于num1中的数字1，第二个数组中数字1右边的下一个较大数字是 3。
     *     对于num1中的数字2，第二个数组中没有下一个更大的数字，因此输出 -1。
     * 示例 2:
     * 
     * 输入: nums1 = [2,4], nums2 = [1,2,3,4].
     * 输出: [3,-1]
     * 解释:
     *     对于num1中的数字2，第二个数组中的下一个较大数字是3。
     *     对于num1中的数字4，第二个数组中没有下一个更大的数字，因此输出 -1。
     * 注意:
     * 
     * nums1和nums2中所有元素是唯一的。
     * nums1和nums2 的数组大小都不超过1000。
     * @param nums1
     * @param nums2
     * @return
     */
//	public int[] nextGreaterElement(int[] nums1, int[] nums2) {
//		int len1 = nums1.length;
//		int len2 = nums2.length;
//		int[] ngArr = new int[len1];
//		for (int i = 0; i < len1; i++) {
//			int greater = -1;
//			for (int j = len2 - 1; j >= 0; j--) {
//				if (nums2[j] == nums1[i]) {
//					ngArr[i] = greater;
//					break;
//				} else if (nums2[j] > nums1[i]) {
//					greater = nums2[j];
//				}
//			}
//		}
//		return ngArr;
//	}
	public int[] nextGreaterElement(int[] nums1, int[] nums2) {
		// 使用Stack和HashMap
		Stack<Integer> stack = new Stack<Integer>();
		Map<Integer, Integer> map = new HashMap<Integer, Integer>(); //<K,V> = <数字 x, 下一个更大元素>
		for (int i = 0; i < nums2.length; i++) {
			while (!stack.isEmpty()) {
				Integer cur = stack.peek();
				if (nums2[i] > cur) {
					map.put(cur, nums2[i]);
					stack.pop();
				} else {
					break;
				}
			}
			stack.push(nums2[i]);
		}
		int len1 = nums1.length;
		int[] ngArr = new int[len1];
		Arrays.fill(ngArr, -1);
		for (int i = 0; i < nums1.length; i++) {
			if (map.containsKey(nums1[i])) {
				ngArr[i] = map.get(nums1[i]);
			}
		}
		return ngArr;
	}
	
    /**
     * 682. 棒球比赛
     * 
     * 你现在是棒球比赛记录员。
     * 给定一个字符串列表，每个字符串可以是以下四种类型之一：
     * 1.整数（一轮的得分）：直接表示您在本轮中获得的积分数。
     * 2. "+"（一轮的得分）：表示本轮获得的得分是前两轮有效 回合得分的总和。
     * 3. "D"（一轮的得分）：表示本轮获得的得分是前一轮有效 回合得分的两倍。
     * 4. "C"（一个操作，这不是一个回合的分数）：表示您获得的最后一个有效 回合的分数是无效的，应该被移除。
     * 
     * 每一轮的操作都是永久性的，可能会对前一轮和后一轮产生影响。
     * 你需要返回你在所有回合中得分的总和。
     * 
     * 示例 1:
     * 
     * 输入: ["5","2","C","D","+"]
     * 输出: 30
     * 解释: 
     * 第1轮：你可以得到5分。总和是：5。
     * 第2轮：你可以得到2分。总和是：7。
     * 操作1：第2轮的数据无效。总和是：5。
     * 第3轮：你可以得到10分（第2轮的数据已被删除）。总数是：15。
     * 第4轮：你可以得到5 + 10 = 15分。总数是：30。
     * 示例 2:
     * 
     * 输入: ["5","-2","4","C","D","9","+","+"]
     * 输出: 27
     * 解释: 
     * 第1轮：你可以得到5分。总和是：5。
     * 第2轮：你可以得到-2分。总数是：3。
     * 第3轮：你可以得到4分。总和是：7。
     * 操作1：第3轮的数据无效。总数是：3。
     * 第4轮：你可以得到-4分（第三轮的数据已被删除）。总和是：-1。
     * 第5轮：你可以得到9分。总数是：8。
     * 第6轮：你可以得到-4 + 9 = 5分。总数是13。
     * 第7轮：你可以得到9 + 5 = 14分。总数是27。
     * 注意：
     * 
     * 输入列表的大小将介于1和1000之间。
     * 列表中的每个整数都将介于-30000和30000之间。
     * @param ops
     * @return
     */
	public int calPoints(String[] ops) {
		int len = ops.length;
		int idx = 0;
		int[] nums = new int[len];
		for (String op : ops) {
			if ("C".equals(op)) {
				idx--;
				continue;
			}
			if ("D".equals(op)) {
				nums[idx] = nums[idx - 1] * 2;
			} else if ("+".equals(op)) {
				nums[idx] = nums[idx - 1] + nums[idx - 2];
			} else {
				nums[idx] = Integer.parseInt(op);
			}
			idx++;
		}
		// sum
		int sum = 0;
		for (int i = 0; i < idx; i++) {
			sum += nums[i];
		}
		return sum;
	}
	
	
	/**
	 * 844. 比较含退格的字符串
	 * 
	 * 给定 S 和 T 两个字符串，当它们分别被输入到空白的文本编辑器后，判断二者是否相等，并返回结果。 # 代表退格字符。
	 * 
	 * 示例 1：
	 * 
	 * 输入：S = "ab#c", T = "ad#c"
	 * 输出：true
	 * 解释：S 和 T 都会变成 “ac”。
	 * 示例 2：
	 * 
	 * 输入：S = "ab##", T = "c#d#"
	 * 输出：true
	 * 解释：S 和 T 都会变成 “”。
	 * 示例 3：
	 * 
	 * 输入：S = "a##c", T = "#a#c"
	 * 输出：true
	 * 解释：S 和 T 都会变成 “c”。
	 * 示例 4：
	 * 
	 * 输入：S = "a#c", T = "b"
	 * 输出：false
	 * 解释：S 会变成 “c”，但 T 仍然是 “b”。
	 *  
	 * 
	 * 提示：
	 * 
	 * 1 <= S.length <= 200
	 * 1 <= T.length <= 200
	 * S 和 T 只含有小写字母以及字符 '#'。
	 */
	public boolean backspaceCompare(String S, String T) {
		Stack<Character> sStack = new Stack<Character>();
		Stack<Character> tStack = new Stack<Character>();
		char[] sArr = S.toCharArray();
		char[] tArr = T.toCharArray();
		for (char ch : sArr) {
			if (ch == '#') {
				if (!sStack.isEmpty()) {
					sStack.pop();
				}
			} else {
				sStack.push(ch);
			}
		}
		for (char ch : tArr) {
			if (ch == '#') {
				if (!tStack.isEmpty()) {
					tStack.pop();
				}
			} else {
				tStack.push(ch);
			}
		}
		while (!sStack.isEmpty() && !tStack.isEmpty()) {
			if (!sStack.pop().equals(tStack.pop())) {
				return false;
			}
		}
		return sStack.isEmpty() && tStack.isEmpty();
	}
	
}
